#define max(a, b) (((a) > (b)) ? (a) : (b))

// step 0# 初始化糖果数组，每个孩子初始1颗糖
int *initCandyArr(int size) {
    int *candyArr = (int*)malloc(sizeof(int) * size);

    for(int i = 0; i < size; ++i)
        candyArr[i] = 1;

    return candyArr;
}

int candy(int* ratings, int ratingsSize) {
    // step 1# 每个孩子至少分到1颗糖果
    int *candyArr = initCandyArr(ratingsSize);

    // step 2# 从左向右遍历：如果当前孩子评分比左边高，就给更多糖果
    for(int i = 1; i < ratingsSize; ++i) {
        if(ratings[i] > ratings[i - 1])
            candyArr[i] = candyArr[i - 1] + 1;
    }

    // step 3# 从右向左遍历：如果当前孩子评分比右边高，确保糖果更多
    for(int i = ratingsSize - 2; i >= 0; --i) {
        if(ratings[i] > ratings[i + 1])
            // step 3.1# 要取 max，防止之前左侧递增时已经给了更高的糖果
            candyArr[i] = max(candyArr[i], candyArr[i + 1] + 1);
    }

    // step 4# 计算所有糖果总和
    int result = 0;
    for(int i = 0; i < ratingsSize; ++i) {
        result += candyArr[i];
    }

    return result;
}
